package com.cat.chapter048;

/**
 * @author cat
 * @description https://leetcode.cn/problems/largest-1-bordered-square/
 * @create 2025/7/17 11:43
 * @since JDK17
 */

public class Solution01 {
    int [][] g;
    public void build(int[][] g, int n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g[i][j] += get(g, i - 1, j) + get(g, i, j - 1) - get(g, i - 1, j - 1);
            }
        }
    }

    public int get(int[][] g, int x, int y) {
        return x < 0 || y < 0 ? 0 : g[x][y];
    }

    public int sum(int a, int b, int c, int d) {
        return get(g, c, d) + get(g, a - 1, b - 1) - get(g, a - 1, b) - get(g, c, b - 1);
    }

    public int largest1BorderedSquare(int[][] grid) {
        int n = grid.length, ans = 1;
        build(grid, n);
        if (grid[n - 1][n - 1] == 0) {
            return 0;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int a = i + ans, b = j + ans, k = ans + 1; a < n && b < n; k++, a++, b++) {
                    if (sum(i, j, a, b) == (k - 1) * 4) {
                        ans = k;
                    }
                }
            }
        }

        return ans;
    }
}